include!(concat!(env!("OUT_DIR"), "/dict.rs"));

pub fn converter(input: &str, tp: &str) -> String {
    match tp {
        "s2t" => s2t(input),
        "t2s" => t2s(input),
        _ => unimplemented!("Illegal convertion type: {tp:?}"),
    }
}

fn s2t(input: &str) -> String {
    query(input, S2T)
}

fn t2s(input: &str) -> String {
    query(input, T2S)
}

fn common_prefix<'a>(a: &'a str, b: &str) -> &'a str {
    let len = a
        .chars()
        .zip(b.chars())
        .take_while(|(a, b)| a == b)
        .map(|(a, _)| a.len_utf8())
        .sum();

    &a[..len]
}

struct QueryOnce<'a> {
    result: Option<&'static str>,
    remaining: &'a str,
}

fn query_once<'a>(input: &'a str, mut dict: &[(&'static str, &'static str)]) -> QueryOnce<'a> {
    let result = {
        let mut input = input;

        loop {
            match dict.binary_search_by_key(&input, |item| item.0) {
                Ok(i) => break Some(dict[i]),
                Err(i) => {
                    let &(word, conv) = dict.get(i.saturating_sub(1)).unwrap();
                    let prefix = common_prefix(input, word);
                    match prefix {
                        "" => break None,
                        p if p == word => break Some((word, conv)),
                        p => {
                            input = p;
                            // The prefix must appear before the current word in the dictionary.
                            dict = &dict[..i];
                        }
                    }
                }
            };
        }
    };

    if let Some((word, conv)) = result {
        QueryOnce {
            result: Some(conv),
            remaining: &input[word.len()..],
        }
    } else {
        QueryOnce {
            result: None,
            remaining: input,
        }
    }
}

fn query(mut input: &str, dict: &[(&'static str, &'static str)]) -> String {
    let mut output = String::new();
    loop {
        if input.is_empty() {
            return output;
        }

        let QueryOnce { result, remaining } = query_once(input, dict);

        match result {
            Some(conv) => {
                output.push_str(conv);
                input = remaining;
            }
            None => {
                // We already know that `input` is not empty.
                let ch = input.chars().next().unwrap();
                output.push(ch);
                input = &input[ch.len_utf8()..];
            }
        }
    }
}
